package com.itsky.java.ai.resultGreen;

import java.util.HashMap;
import java.util.Map;

public class LongStringWithoutRepeatCharacters {
    public static void main(String[] args) {
        String str = "good goos Study";
        System.out.println(getUniqueSubstring(str));
        String str1 = "hello the boy";
        System.out.println(getUniqueSubstring(str1));
    }

//    从一段字符串中截取最长不重复子串(区分大小写、时空复杂度低)
    private static String getUniqueSubstring(String input) {
            if (input == null || input.length() == 0)
            {return "";}
            /*滑动窗口方案,挨个比较，不重复则存入HashMap*/
            Map<Character, Integer> CharIndexmap = new HashMap<>();
            int maxLength = 0;
            int startIndex = 0;
            int resultStart = 0;
            for (int endIndex = 0; endIndex < input.length(); endIndex++){
                final char currentChar = input.charAt(endIndex);
                if (CharIndexmap.containsKey(currentChar)){
                    startIndex = Math.max(startIndex, CharIndexmap.get(currentChar) + 1);
                }
//                调整字符串最新起始位置和字符内容
                CharIndexmap.put(currentChar, endIndex);
//                调整最长子串长度和最新起始位置
                if (endIndex - startIndex + 1 > maxLength){
                    maxLength = endIndex - startIndex + 1;
                    resultStart = startIndex;
                }
            }
//            从最长子串起始位置开始截取最长子串，用substring方法截取
            return input.substring(resultStart, resultStart + maxLength);
        }
    }
